474F - Ant colony - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define maxn 100010
#define inf 1e9

struct qDT{
    int g, m, c;
    qDT(){}
    qDT(int g, int m, int c){
        this->g = g;
        this->m = m;
        this->c = c;
    }
	void print(){
        cout << g << " " << m << " " << c << endl;
    }
};

int a[maxn], segTree[4 * maxn], gcdTree[4 * maxn], cnt[4 * maxn];

void build(int at, int l, int r){
    if(l == r){
        segTree[at] = a[l];
        gcdTree[at] = a[l];
        cnt[at] = 1;
        return;
    }
    int mid = (l + r) / 2;
    build(at * 2, l, mid);
    build(at *2 + 1, mid + 1, r);
    int x = segTree[at * 2];
    int y = segTree[at * 2 + 1];
    segTree[at] = min(x, y);
    gcdTree[at] = __gcd(gcdTree[at * 2], gcdTree[at * 2 + 1]);
    if(x == y)
        cnt[at] = cnt[at * 2] + cnt[at * 2 + 1];
    else if(x < y)
        cnt[at] = cnt[at * 2];
    else
        cnt[at] = cnt[at * 2 + 1];
}

qDT query(int at, int L, int R, int l, int r){
    if(r < L || R < l) return qDT(0, 1e9, -1);
    if(l <= L && R <= r)
        return qDT(gcdTree[at], segTree[at], cnt[at]);
    int mid = (L + R) / 2;
    qDT x = query(at * 2, L, mid, l, r);
    qDT y = query(at * 2 + 1, mid + 1, R, l, r);
    int g = __gcd(x.g, y.g);
    if(x.m == y.m)
        return qDT(g, x.m, x.c + y.c);
    else if(x.m < y.m)
        return qDT(g, x.m, x.c);
    else
        return qDT(g, y.m, y.c);
}

int main(){
    int i, j, k;
    int n, m, t;
    int l, r;
    cin >> n;
    for(i = 1; i <= n; i++)
       cin >> a[i];
    build(1, 1, n);
    cin >> t;
    while(t--){
        cin >> l >> r;
        qDT temp = query(1, 1, n, l, r);
        if(temp.g == temp.m)
            cout << r - l + 1 - temp.c;
        else
            cout << r - l + 1;
        cout << endl;
    }
}